This application relates to Oblivious Random Access Memory (ORAM), and more particularly relates to an approach in which a privacy and performance characteristics of an ORAM can be configured (“tuned”).
Cloud storage and computing are important tools to outsource data but have given rise to significant privacy concerns due to the non-local nature of data storage. Though encryption goes a long way in assuring data confidentiality, recent work [IKK14, DJR13] has shown that encryption is not sufficient. Encryption does not hide memory access patterns; an untrusted storage server can thus perform traffic analysis of memory access patterns to compromise client privacy. The work of Islam et al. has shown the leakage of sensitive keyword information by performing traffic analysis of access patterns over encrypted email [IKK14]. Similarly, Dautrich et al. have shown that access patterns over database tuples can leak ordering information [DJR13].
Oblivious RAM (ORAM), first introduced by Goldreich and Ostrovsky [GO96, Gol87], is a cryptographic primitive which allows a client to protect its data access pattern from an untrusted server storing the data. Since its introduction, substantial progress has been made by the research community in developing novel and efficient ORAM schemes [SVDS+13, RFK+b, GGH+13, DSS12, SSS11, RFK+a, SS13]. Recent work has also shown the promise of using ORAMs as a critical component in developing protocols for cryptographic primitives such as Secure Multi-Party Computation [GGH+13].
However, ORAM schemes can incur a large overhead in terms of bandwidth that renders them impractical. For example, even the most efficient ORAM protocols [SVDS+13, SSS11, RFK+b] incur a logarithmic overhead compared to conventional RAMs (e.g., greater than 100 times increase in communication including constants). This significantly impacts the throughput and latency of memory accesses, and presents a bottleneck for real-world deployment of ORAMs in high-performance and bandwidth constrained applications. The lack of low-bandwidth ORAMs, despite considerable efforts from the security community, is an undeniable indicator for the need of a new approach.